package com.zdp.others;

public class kmp {
    public static void main(String[] args) {
        //测试一下
        kmp demo = new kmp();
        String value = "xxswfsafababacweqxsac";
        String pattern = "ababac";
       // System.out.println(demo.getIndexOf_KMP(value, pattern));
        System.out.println(demo.getNext(pattern));
    }
    /*
    * value:主串
    * pattern:子串
    * */
    public int getIndexOf_KMP(String value,String pattern){
        if(pattern==null||value==null||pattern.length()>value.length()
        ||pattern.length()<1)
            return -1;
        //首先获得子串的next数组
        int[] next = getNext(pattern);
        //然后根据next数组来进行加速
        int pos = 0;
        int mpos = 0;
        char[] p = pattern.toCharArray();
        char[] v = value.toCharArray();
        while(pos<pattern.length()&&mpos<value.length()){
            //开始匹配
            if(p[pos]==v[mpos]){
                pos++;
                mpos++;
            }else if(next[pos]==-1){
                //说明已经无法匹配了，主串前进
                mpos++;
            }else{
                //如果不匹配,pos的值根据next数组的值来更新
                pos = next[pos];
            }
        }
        return pos==pattern.length()?mpos-pattern.length():-1;

    }

    public int[] getNext(String value){
        int length = value.length();
        if(length==1)
            return new int[]{-1};
        int[] next = new int[length];
            next[0] = -1;
            next[1] = 0;
            int cn = 0; //表示索引的最长前后缀匹配长度
            int pos = 2;
            //开始计算
           while(pos<length){
               if(value.charAt(pos-1)==value.charAt(cn)){
                   //如果匹配，就在原来的基础上+1
                   next[pos++]=++cn;
               }else if(cn>0){//如果不匹配，且还可以划分，就进行划分
                   //为什么是cn>0 而不是cn>=0,这是因为我们已经进行比较判断过了
                   //也就是说，cn=0的情况我们已经在上面的if进行判断了，如果cn=0还是
                   //不匹配的话，也就无法再划分了
                   cn = next[cn];
               }else{
                   next[pos++] = 0;
               }
           }
        System.out.println("==============next===========");
           for(int i=0;i<next.length;i++){
               System.out.println("next["+i+"] = "+next[i]);
           }
        System.out.println("==============================");
        return next;
    }
}
